package xiaolong.arithmetic.fun_lib;

/**
 * Created by xinxiaolong on 2020/10/23.
 * email：xinxiaolong123@foxmail.com
 * <p>
 * <p>
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 示例：
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * [9]
 * [1,9,9,9,9,9,9,9,9,9]
 */
public class SumOfTwo {

    public static void main(String[] agr) {

        ListNode n1 = getListNode(9);
        printListNode(n1);

        System.out.println("=====================================================");
        ListNode n2 = getListNode2(999999999);

        printListNode(n2);

        System.out.println("=====================================================");

        System.out.println(getIntValue(n1));
        System.out.println(getIntValue(n2));

        System.out.println("=====================================================");

        ListNode node = addTwoNumbers2(n1, n2);

        printListNode(node);

    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * ***************************************************************************************************************************************************************************************************************************************
     * ****************************************************************************************************转int 再计算，出现了数据溢出的问题******************************************************************************************************
     * ***************************************************************************************************************************************************************************************************************************************
     * ***************************************************************************************************************************************************************************************************************************************
     */
    /**
     * 自己最简单的思路，将链表解析成int。但是会有数据溢出的问题。
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int num1 = getIntValue(l1);
        int num2 = getIntValue(l2);
        int sum = num1 + num2;
        return getListNode(sum);
    }

    /**
     * 将node转成数字
     *
     * @param node
     * @return
     */
    private static int getIntValue(ListNode node) {
        int num = 0;
        int index = 0;
        while (node != null) {
            num = node.val * (int) Math.pow(10, index) + num;
            node = node.next;
            index++;
        }
        return num;
    }

    /**
     * 将数字转成链表
     *
     * @param number
     * @return
     */
    private static ListNode getListNode(int number) {
        ListNode firstNode = null;
        ListNode mNode = null;

        while (number > 0) {
            int value = number % 10;
            number = number / 10;
            if (mNode == null) {
                mNode = new ListNode(value);
                firstNode = mNode;
            } else {
                ListNode node = new ListNode(value);
                mNode.next = node;
                mNode = node;
            }
        }
        return firstNode == null ? new ListNode(0) : firstNode;
    }


    /**
     * 将数字转成链表,强制设置10位。
     *
     * @param number
     * @return
     */
    private static ListNode getListNode2(int number) {
        ListNode firstNode = null;
        ListNode mNode = null;

        while (number > 0) {
            int value = number % 10;
            number = number / 10;
            if (mNode == null) {
                mNode = new ListNode(value);
                firstNode = mNode;
            } else {
                ListNode node = new ListNode(value);
                mNode.next = node;
                mNode = node;
            }
        }
        ListNode node = new ListNode(1);
        node.next = firstNode;
        return node;
    }

    private static void printListNode(ListNode node) {
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }


    /**
     * ***************************************************************************************************************************************************************************************************************************************
     * ***************************************************************************************************************************************************************************************************************************************
     * *************************************************************************************************标准答案*******************************************************************************************************************************
     * ***************************************************************************************************************************************************************************************************************************************
     * ***************************************************************************************************************************************************************************************************************************************
     */
    /**
     * 标准答案
     */
    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }


    /**
     * ***************************************************************************************************************************************************************************************************************************************
     * ***************************************************************************************************************************************************************************************************************************************
     * *************************************************************************************************参考标准答案****************************************************************************************************************************
     * ***************************************************************************************************************************************************************************************************************************************
     * ***************************************************************************************************************************************************************************************************************************************
     */

    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode preNode = null, headNode = null;
        int num1 = 0;
        int num2 = 0;
        int carry = 0;
        int sum = 0;

        while (l1 != null || l2 != null) {
            num1 = 0;
            num2 = 0;
            if (l1 != null) {
                num1 = l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                num2 = l2.val;
                l2 = l2.next;
            }

            sum = (num1 + num2 + carry) % 10;
            carry = (num1 + num2 + carry) / 10;

            if (headNode == null) {
                headNode = new ListNode(sum);
                preNode = headNode;
            } else {
                preNode.next = new ListNode(sum);
                preNode = preNode.next;
            }
        }

        if (carry > 0) {
            preNode.next = new ListNode(carry);
        }

        return headNode;
    }
}
